﻿//42. 接雨水
//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

//单调栈

class Solution
{
    vector<int> sta;
public:
    int trap(vector<int>& height)
    {
        //单调栈 搜索每个位置 左大 右大
        int ans = 0;
        int n = height.size();
        if (n <= 2)    return 0;
        sta.push_back(0);
        for (int i = 1; i < n; i++)
        {
            //当前 < 栈顶
            if (height[i] < height[sta.back()])
            {
                //压栈
                sta.push_back(i);
            }
            else if (height[i] == height[sta.back()])
            {
                sta.pop_back();
                sta.push_back(i);
            }
            else
            {
                //循环出栈
                while (!sta.empty() && height[i] > height[sta.back()])
                {
                    //低
                    int cur = sta.back();
                    sta.pop_back();
                    //左侧最大值
                    if (!sta.empty())
                    {
                        int leftmax = sta.back();
                        int rightmax = i;
                        int h = min(height[leftmax], height[rightmax]) - height[cur];
                        ans += (rightmax - leftmax - 1) * h;
                    }
                }
                sta.push_back(i);
            }
        }
        return ans;
    }
};